package src.list;

/**
 * @author starsea
 * @date 2024-08-15 10:49
 */

public class MyLinkedList {
    static class ListNode {
        int val;
        ListNode pre;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    ListNode head;
    ListNode last;
    int usedSize;

    //void createLinkedList() {
    //    ListNode node1 = new ListNode(1);
    //    ListNode node2 = new ListNode(2);
    //    ListNode node3 = new ListNode(3);
    //    ListNode node4 = new ListNode(4);
    //    ListNode node5 = new ListNode(5);
    //    ListNode node6 = new ListNode(6);
    //    node1.next = node2;
    //    node2.next = node3;
    //    node3.next = node4;
    //    node4.next = node5;
    //    node5.next = node6;
    //    node6.pre = node5;
    //    node5.pre = node4;
    //    node4.pre = node3;
    //    node3.pre = node2;
    //    node2.pre = node1;
    //    head = node1;
    //    last = node6;
    //}
void disPlay()
{
    ListNode cur=head;
    for(int i=0;i<usedSize;i++)
    {
        System.out.print(cur.val+" ");
        cur=cur.next;
    }
    System.out.println();
}
    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (usedSize == 0) {
            head = last = node;
        } else {
            node.next = head;
            head.pre = node;
            head = node;
        }
        usedSize++;

    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (usedSize == 0) {
            head = last = node;
        } else {
            last.next=node;
            node.pre=last;
            last=node;
        }
        usedSize++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        if(index<0 || index>=usedSize)
        {
            System.out.println("输入不合法，无法插入");
            return;
        }
        ListNode node=new ListNode(data);
        ListNode cur=head;
        for(int i=0;i<index;i++)
        {
            cur=cur.next;
        }
        node.next=cur.next;
        node.pre=cur;
        cur.next.pre=node;
        cur.next=node;
        usedSize++;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
       ListNode cur=head;
       while(cur!=null)
       {
           if(cur.val==key)
           {
               return true;
           }
           else
           {
               cur=cur.next;
           }
       }
       return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        ListNode cur=head;
        while (cur!=null)
        {
            if(cur.val==key)
            {
                break;
            }
            cur=cur.next;
        }
        if(cur==head)
        {
            head=cur;
            head=head.next;
            head.pre=null;
            cur.next=null;
        }
        else if(cur==last)
        {
            last=last.pre;
            last.next=null;
            cur.pre=null;
        }
        else {
           cur.next.pre=cur.pre;
           cur.pre.next=cur.next;
        }
        usedSize--;
    }
}
